#include<iostream>
#include<string>
#include<vector>
using namespace std;


//14.最长公共子串
string merge(vector<string>& strs,int left,int right){
    if(left>right){
        return "";
    }
    if(left==right){
        return strs[left];
    }

    //求出中间值
    int mid = left + (right - left) / 2;
    //递归
    string s1=merge(strs,left,mid);
    string s2 = merge(strs, mid + 1, right);

    //查找左右区间返回两个字符串的公共前缀
    string ret;
    for(int i=0;i<s1.size()&&i<s2.size();i++){
        if(s1[i]==s2[i]){
            ret += s1[i];
        }
        else{
            break;
        }
    }

    return ret;
}
string longestCommonPrefix(vector<string>& strs){
    return merge(strs, , 0, strs.size() - 1);
}

//最长回文子串
string longestPalindrome(string s){
    int begin = 0, len = 0;
    //中心扩展算法
    for (int i = 0; i < s.size(); i++){
        //先做一次奇数长度的扩展
        int left = i, right = i;
        while(left>=0&&right<s.size()&&s[left]==s[right]){
            left--;
            right++;
        }
        if(right-left-1>len){
            begin = left + 1;
            len = right - left - 1;
        }

        //再做一次偶数长度的扩展
        int left = i, right = i + 1;
        while(left>=0&&right<s.size()&&s[left]==s[right]){
            left--;
            right++;
        }
        if(right-left-1>len){
            begin = left + 1;
            len = right - left - 1;
        }
    }

    return s.substr(begin, len);
}

//二进制求和
string addBinary(string a, string b){
    //先将两个字符串逆序
    reverse(a.begin(),a.end());
    reverse(b.begin(), b.end());

    //n表示进位
    int n = 0;
    string ret;
    for (int i = 0; i < a.size() || i < b.size() || n == 1;i++){
        if(i<a.size()){
            n += (a[i] - '0');
        }
        if(i<b.size()){
            n += (b[i] - '0');
        }
        if(n==0){
            ret += '0';
        }
        else if(n==1){
            ret += '1';
            n = 0;
        }
        else if(n==2){
            ret += '0';
            n = 1;
        }
        else{
            ret += '1';
            n = 1;
        }
    }

    return reverse(ret.begin(), ret.end());
}

//43.字符串相乘
string multiply(string num1, string num2){
    //处理前导0的情况
    if(num1[0]=='0'||num2[0]=='0'){
        return "0";
    }
    //先将两个字符串逆序
    reverse(num1.begin(), num1.end());
    reverse(num2.begin(), num2.end());
    //先处理无进位相乘
    vector<int> nums(num1.size()+num2.size()-1);

    for (int i = 0; i < num2.size(); i++){
        for (int j = 0; j < num1.size(); j++){
            nums[i + j] += (num1[j] - '0') * (num2[i] - '0');
        }
    }

    //n表示进位
    int n = 0;
    string ret;
    for (int i = 0; i < nums.size() || n;i++){
        if(i<nums.size()){
            n += nums[i];
        }

        ret += ((n % 10) + '0');
        n /= 10;
    }

    //结果逆序
    reverse(ret.begin(), ret.end());
    return ret;
}

int main(){

    return 0;
}